package com.nanbei.recursion;

/**
 * @ClassDescription:  单路递归
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/11/21 14:04
 */
public class SingleRecursion {

    /**
     *  阶乘
     * @param num 阶乘数
     * @return 阶乘结果
     */
    public static int jieChen(int num){
        if (num == 1){
            return 1;
        }

        return num * jieChen(num -1);
    }

    /**
     * 通过阶乘 反向打印字符串
     * @param str 字符串
     */
    public static void reversePrint(String str , int index) {

        if (index == str.length()){
            return;
        }

        reversePrint(str,index+1);

        System.out.println(str.charAt(index));

    }


    /**
     * 通过递归进行二分查找
     * @param nums 一维数组
     * @param pre 前指针 0
     * @param last 尾指针 nums.length-1
     * @param target 目标值
     * @return 目标值下标
     */
    public static int recursion(int[] nums, int pre,int last,int target){

        if (pre>last){
            return -1;
        }

        int mid = (pre + last) >>>1;

        if (nums[mid] > target){
            last = mid -1;
        }else if (target > nums[mid]){
            pre = mid+1;
        }else {
            return mid;
        }

        return recursion(nums,pre,last,target);

    }


    /**
     * 通过递归进行冒泡排序  每经过一次递归会将最大的数据排到最后
     * @param nums 待排序数组
     * @param height nums.length-1 已排序的范围下标
     *
     */
    public static void bubble(int[] nums, int height){

        if (0 == height){
            return;
        }

        for (int i = 0; i < height; i++) {
            if (nums[i] > nums[i+1]){
                int temp =  nums[i+1];
                nums[i+1] = nums[i];
                nums[i] = temp;
            }
        }
        bubble(nums,height-1);


    }

    /**
     * 通过递归进行冒泡排序(优化后)
     * 每经过一次递归会将最大的数据排到最后
     * 新增一个flag标识 在循环中两个数进行比较，如果位置进行调换则flag进行替换成交换的下标
     * 如果在后续的比较中没有发生位置呼唤，则证明在flag下标以后的数据都是有序的，则下次直接遍历到flag下标即可。
     * @param nums 待排序数组
     * @param height nums.length-1 已排序的范围下标
     *
     */
    public static void bubbleUp(int[] nums, int height){

        if (0 == height){
            return;
        }
        int flag = 0 ;

        for (int i = 0; i < height; i++) {
            if (nums[i] > nums[i+1]){
                int temp =  nums[i+1];
                nums[i+1] = nums[i];
                nums[i] = temp;
                flag = i;
            }
        }
        bubbleUp(nums,flag);

    }


    /**
     * 通过递归进行插入排序
     * @param nums 待排序数组
     * @param low 初始值为 1 未排序区域的左边界
     */
    public static void insertion(int[] nums, int low){

        if (low == nums.length){
            return;
        }

        int temp = nums[low];
        int i =low - 1; //已排序区域指针右边界

        while (i>=0 && nums[i] >temp){  //没有找到插入位置
            nums[i+1] = nums[i]; //空出插入位置
            i--;
        }
        //找到了插入位置
        if (low != i+1){
            nums[i+1] = temp;
        }

        insertion(nums,low+1);

    }


}
